package threeSum15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class threeSum {

    public static void main(String[] args) {
        threeSum threeSum = new threeSum();
        //int [] a = {-1,0,1,1,2,2,-1,-4,-4};
        int [] a = {3,0,-2,-1,1,2};
        List<List<Integer>> lists = threeSum.threeSumR(a);
        System.out.println(lists);
        //需要去重，如果不去重则会出现[[-4, 2, 2], [-4, 2, 2], [-1, -1, 2]]
    }


    public List<List<Integer>> threeSumR(int[] nums) {
        //先排序，之后循环数组每一个的时候固定当地循环的值，之后使用双指针进行元素相加看结果是否是当前值
        List<List<Integer>> ans = new ArrayList();
        if(nums == null || nums.length < 3) return ans;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            int L = i+1;
            int R = nums.length-1;
            if (i>0&&nums[i]==nums[i-1]){//去重，因为是排好序的，如果两个挨着的元素相同则会出现重复
                continue;
            }

            //双指针左边小于右边
            while (L<R){
                int sum =nums[i]+ nums[L] + nums[R];
                //当前循环的元素与双指针指向元素的和=0
                if(sum==0){
                    ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    //双指针内收
                    while (L<R && nums[L]==nums[L+1]){
                        //如果相邻元素相同则左侧指针继续右移目的是去重
                        L++;
                    }
                    while (L<R && nums[R]==nums[R-1]){
                        R--;
                    }
                    L++;
                    R--;
                }else if(sum<0){
                    L++;
                }else if(sum>0){
                    R--;
                }
            }
        }
        return ans;
    }

}
